In many digital-logic systems, multiple sources, or “masters,” share access to a common resource, or “slave.” For example, multiple processors or local memories (examples of masters) of a “system on a chip” (SoC) may share an on-chip or off-chip main memory (an example of a slave). Data flow from and to the common memory is typically controlled by a dynamic memory controller (DMC). The DMC may, in a simple implementation, process requests from the masters in the order in which they are received, i.e., on a “first-come, first-served” basis. Often, however, the resulting order of transactions entails frequent switching between different masters and/or between read transactions and write transactions; switching is associated with a processing overhead that limits data throughput and, thus, the overall transfer rate. For example, when transferring data from and to dynamic random access memory (DRAM), switching from read to write transactions may carry an access-time penalty of seven clock cycles, and the reverse change in direction may carry a penalty of nine clock cycles; during this time, data transfer cannot take place.
Accordingly, it may be more efficient to process transactions out of order, e.g., to schedule transactions from the same master and/or in the same direction back-to-back. A commonly used architecture facilitating such out-of-order transaction execution is the Advanced Extensible Interface (AXI) defined under the Advanced Microcontroller Bus Architecture (AMBA). AXI enables association of an identification (ID) tag with each transaction; transactions having the same ID generally have internal dependencies and should be completed in order, whereas transactions having different IDs may be completed in any order. Thus, if different groups of IDs (which typically share a common ID portion) correspond to different masters requesting the respective transactions, AXI facilitates scheduling the transactions (via a suitable controller) in an order such that all transactions from the same master are completed before transaction processing moves on to the next master. Similarly, all read transactions may be executed before any write transactions are processed, or vice versa.
While scheduling all transactions in the same direction (or from the same master) in succession will generally maximize throughput, it can lead to starvation of the other direction (or of other masters). For example, as write transactions are executed, new write requests may continuously come in, and as a result, the read transactions may be delayed indefinitely. Accordingly, there is a need for scheduling approaches that balance read transactions and write transactions (or transactions from different masters) in a manner that optimizes the trade-off between throughput and the prevention of stalls in one direction (or starvation of some masters).